

			LABIRINT
		       ----------

	Tom si Jerry se afla intr-un labirint dreptunghiular de dimensiuni mxn (1<=m,n<=100).Scrieti
un program care determina in mai putin de 1 secunda lungimea drumului minim dintre pozitiile celor
doi, precum si numarul de drumuri de lungime minima dintre cele doua pozitii.
	Fiecare casuta din labirint poate fi despartita de cele patru casute vecine prin ziduri;
in cazul in care intre doua casute vecine nu exista un zid, exista posibilitatea deplasarii din
una dintre aceste casute in alta.
	Datele de intrare se citesc din fisierul "TOMJERRY.IN" care va contine pe prima linie nume-
rele m si n, separate printr-un singur spatiu, pe a doua linie patru numere intregi (x1 y1 x2 y2)
reprezentand pozitiile lui Tom, respectiv Jerry. Pe urmatoarele m linii se afla cate n numere na-
turale din intervalul [0,15] care reprezinta codificarea caracteristicilor fiecarei casute.
	Fiecareia dintre cele 4 directii ii corespunde un bit din reprezentarea numarului respec-
tiv (bitul 0 corspunde directiei Nord; bitul 1 directiei Est; bitul 2 directiei Sud; bitul 3 direc-
tiei Vest).
	In cazul in care intr-o anumita directie exista zid, valoarea bitului corespunzator va fi
1, in caz contrar 0. De exemplu, pentru o casuta care are ziduri la Vest si la Nord codificarea va
fi 9=1001.

	Datele de iesire vor fi scrise in fisierul "TOMJERRY.OUT" care va contine doua linii; pe
prima linie va aparea lungimea drumului minim dintre pozitiile celor doi, iar pe a doua linie
numarul de drumuri de lungime minima care exista intre cele doua pozitii.

EXEMPLU:
TOMJERRY.IN		TOMJERRY.OUT
4 4			7
1 1 4 4			2
11 9 7 11
12 4 1 6
13 3 8 3
13 4 4 6

OBSERVATII:
1) Nu exista iesire din labirint, adica celulele de pe margine vor avea intotdeauna ziduri spre
exterior.
2) Exista intotdeauna un drum de la pozitia lui Tom la cea a lui Jerry.
3) Nu vor aparea contradictii in descrierea casutelor labirintului. De exemplu, daca o casuta
are zid inspre Sud, atunci casuta din Sud va avea obligatoriu zid inspre Nord.